/*
 * @Author: szx
 * @Date: 2022-03-24 15:10:28
 * @LastEditTime: 2022-03-24 15:17:13
 * @Description:
 * @FilePath: \leetcode\剑指offer\38\38.js
 */
/**
 * @param {string} s
 * @return {string[]}
 */
var permutation = function (s) {
    const arr = s.split('');
    const n = arr.length;
    arr.sort();
    const res = [];
    const used = new Array(n).fill(false);
    const backTrace = (path, index) => {
        if (path.length == n) {
            res.push(path.join(''));
            return;
        }
        for (let i = 0; i < n; i++) {
            if (used[i] || (i > 0 && arr[i] == arr[i - 1] && !used[i - 1])) continue;
            path.push(arr[i]);
            used[i] = true;
            backTrace(path, i);
            used[i] = false;
            path.pop();
        }
    };
    backTrace([], 0);
    return res;
};
console.log(permutation('aab'));
console.log(permutation('abc'));
